Many color image output devices which are driven by digital color image databases employ an image frame buffer the capacity of which is considerably less than that of the encoding resolution into which an original color image has been digitized by a color opto-electronic imaging device, such as a high precision digitizing color camera. A typical example of this mismatch in data precision is the use of an eight bit frame buffer in association with a color image output device, such as a color display monitor, to store a digital color image having a data precision of-twenty-four bits (eight bits per color per pixel).
Since the output device (e.g. color display) usually has a resolution of eight bits per color at the input of each of three respective digital-to-analog converters which drive its red, green and blue signal ports, it is possible for the output device to replicate any of the colors within the original image, as long as a code representative of that particular color is stored in the frame buffer. Unfortunately, in the previous example, the limited capacity of the frame buffer means that only 256 out of 16 million possible colors codes are available to define the original digital color image may be stored. As a consequence, it is necessary to generate a color conversion mechanism through which each of the colors of the original input image (e.g. out of a possibility of 2.sup.24 =1.6.times.10.sup.7 colors) is effectively transformed into one of a lesser number of output colors (e.g. 2.sup.8 =256 colors) for driving the display.
Color conversion quantization has been the fundamental technique for reducing the color code resolution of the original color image size to a limited palette of color codes that can be accommodated by the frame buffer and which are selected to as faithfully as possible replicate the color characteristics of the original image. Color conversion quantization typically has involved some form of vector quantization and operates to minimize an objective error criterion (usually mean squared error).
One class of quantization techniques, as described in articles by P. Heckbert, entitled "Color image quantization for frame buffer display," Computer Graphics, Vol. 16, No.3, pp 297-307, July 1972, G. Braudaway, entitled "A procedure for optimum choice of a small number of colors from a large color palette for color imaging," Electronic Imaging '87, San Francisco Calif., 1987 and R. Gentile et al entitled "Quantization of color images based on uniform color spaces," Journal of Imaging Technology, Vol. 16, No. 1, pp.12-21, Feb 1990, selects an initial color palette and iteratively refines it using the algorithm described in an article by Y. Linde et al, entitled "An algorithm for vector quantizer design," IEEE Transactions on Communications, Vol. COM-28, pp 84-95, Jan. 1980. While these vector quantization mechanisms yield high quality images, they are very computationally intensive.
Another approach, described in an article by R. Balasubramanian et al, entitled "A new approach to palette selection for color images," Journal of Imaging Technology, Vol. 17, No. 6, pp.284-290, Dec. 1991, and based upon a clustering vector quantization technique proposed in an article by W. Equitz entitled "A new vector quantization algorithm," IEEE Transactions on Acoustics, Speech, Signal Processing, Vol. 37, No. 10, pp 1568-1575, Oct. 1989, starts with all of the colors of an image and groups colors into clusters by merging one nearest neighbor pair of clusters at a time until the number of clusters equals the desired number of palette colors. The centroids of the clusters are selected as the palette colors. Tree structures are used to perform efficient nearest neighbor searches. In addition, this scheme employs histogramming to reduce the number of initial colors and a spatial activity weighting to take into account the sensitivity of the human visual system to quantization errors in relatively `smooth` regions of the image.
A third class of vector quantization algorithms uses splitting techniques to divide the color space into smaller sub-regions and selects a representative palette color from each sub-region. In general, splitting techniques are computationally more efficient than either the iterative or merging techniques and can provide a structure to the color space that enables efficient pixel mapping at the output.
One of these splitting techniques, termed a `median cut` algorithm, recursively splits a region into two subregions by locating a plane perpendicular to the coordinate axis having the greatest range (where the range is the difference between the maximum and minimum values of that coordinate) and which passes through the median point of that coordinate axis.
A second splitting technique is a variance-based algorithm which splits the region having the largest total squared error (TSE). Data points are projected onto each of the coordinate axes and the projected TSEs computed. The region is then split along that axis yielding the smallest sum of projected TSEs from the two resulting sub-regions. For a detailed discussion of the variance splitting algorithm attention may be directed to an article by S. Wan et al, entitled "Variance based color image quantization for frame buffer display" COLOR Research and Applications, Vol. 15, No. 1, pp 52-58 Feb. 1990.
A third splitting algorithm, which is the most optimal in a quantitative sense, is the binary splitting algorithm. The binary splitting algorithm passes a splitting plane through the centroid of all the colors of the region such that the splitting plane is oriented perpendicular to the direction of maximum total squared variation. The latter is derived from the principal eigenvalue and eigenvector of the covariance matrix of the data in that region. At each step the region to be split is that with the largest associated principal eigenvalue. The binary splitting algorithm also incorporates spatial activity measures to enhance the subjective quality of the image. For a detailed discussion of the binary splitting algorithm attention may be directed to an article by M. Orchard et al, entitled "Color quantization of images", IEEE Transactions on Signal Processing Vol. 39, No. 12, pp 2677-2690, Dec. 1991.